Đỗ Phục Uy là người Chương Khâu, Tề châu (齊州, nay gần tương ứng với Tế Nam, Sơn Đông). Ông được mô tả là có tính phóng khoáng khi còn trẻ tuổi, không lo kiếm sống, nhà nghèo, không thể tự nuôi sống bản thân. Hảo bằng hữu Phụ Công Thạch thường trộm cừu của thúc để trao cho Đỗ Phục Uy, khiến cả hai bị quan phủ chú ý. Hai người vì thế đã chạy trốn, và họ tập hợp người nổi dậy chống lại triều đình Tùy, ông 16 tuổi (15 tuổi tây) vào năm 613 hoặc một thời gian ngắn trước đó. Ông được mô tả là một người dũng mãnh, bất cứ khi nào quân nổi dậy giao chiến, Đỗ Phục Uy luôn ở trước tiên, và bất cứ khi nào rút lui, ông luôn đi sau cùng. Khi đó trong vùng còn có quân nổi dậy của Miêu Hải Triều (苗海潮), Đỗ Phục Uy phái Phụ Công Thạch đến nói với Miêu:

Nay chúng ta cùng chịu khổ từ sự cai trị của triều Tùy, đều vùng dậy làm đại nghĩa. Chúng ta phân chia lực lượng nên thế yếu, thường lo sợ sẽ bị bắt. Sao ta không hợp lại để mạnh lên, không còn phải lo lắng trước quân Tùy nữa. Nếu ngài thấy mình có khả năng làm chủ, ta sẽ kính trọng mà tuân theo. Nếu ngài tự thấy không kham được, có thể nghe theo mệnh lệnh của ta. Nếu không, chúng ta sẽ phân cao thấp bằng một trận chiến.

Miêu Hải Triều sợ hãi, đem kì chúng quy phục Đỗ Phục Uy. Năm Đại Nghiệp thứ 9 (613), Đỗ Phục Uy suất chúng nhập Trường Bạch Sơn (長白山, nay thuộc Tân Châu, Sơn Đông), song sau đó lại tiến về phía nam, vượt Hoài Hà, tự xưng là tướng quân. Giang Đô lưu thủ khiển hiệu úy Tống Hạo (宋顥) suất binh tấn công Đỗ Phục Uy. Đỗ Phục Uy giả vờ bại trận và lừa quân Tùy mắc kẹt trong một đầm lầy, sau đó phóng hỏa đốt cháy cây cối trong đầm lầy, nhiều lính Tùy bị vây hãm trong đầm lầy và bị lửa thiêu chết. Ông giết chết một thủ lĩnh nổi dậy khác là Triệu Phá Trận (趙破陣), thu giữ binh mã của Triệu. Một thủ lĩnh nổi dậy khác là Lý Tử Thông hội quân với Đỗ Phục Uy vào năm 615, song sau đó lại cố gắng ám sát Đỗ Phục Uy. Đỗ Phục Uy thoát chết song bị thương nặng, được thuộc hạ là Vương Hùng Đản (王雄誕) cứu giúp kịp thời. Sau đó, tướng Tùy là Lai Chỉnh (來整) tiến công và đánh bại Đỗ Phục Uy, ông chạy trốn nhờ công của Vương Hùng Đản và Vương thị- thê của thuộc hạ là Tây Môn Quân Nghi (西門君儀). Quân của Đỗ Phục Uy tan rã, song ông đã tập hợp lại lực lượng ngay sau đó.

Cũng trong khoảng thời gian này, Đỗ Phục Uy tuyển chọn 30 tráng sĩ trong số binh lính của mình, và xem họ là "dưỡng tử", mặc dù khi đó ông mới có 17 tuổi. Những người tài cán nhất trong số các "dưỡng tử" này là Vương Hùng Đản và Khám Lăng (闞稜). Do Đỗ Phục Uy và Phụ Công Thạch là hảo bằng hữu và xem nhau như huynh đệ, các binh sĩ xem Đỗ Phục Uy là "cha", và xem Phụ Công Thạch là "chú".